/*
 * =====================================================================================
 *
 *       Filename:  josephus.c
 *
 *    Description: josephus problem
 *
 *        Created:  2020-05-30 10:49
 *
 *         Author:  limingle
 *          Email:  lml@xdja.com
 *   Organization:  XDJA Tech.CO.ltd.
 *
 * =====================================================================================
 */

#include <stdio.h>

// 用迭代的方式演绎一遍递归的过程。
// f(1) = 1;
// f(2) = ( M + f(1) -1 ) % 2 + 1
// ......
// f(T) = ((M + f(T-1)) -1) % T + 1
int josephus(const unsigned int T, const unsigned int M)
{
    unsigned int the_lucky_dog = 1;
    for (int i = 1; i < T; i++) {
        the_lucky_dog = (the_lucky_dog +  M - 1) % (i + 1) + 1;
    }

    return the_lucky_dog;
}

int main(int argc, const char *argv[])
{
    printf("input Total number of people: ");
    unsigned int T = 0;
    scanf("%u", &T);

    printf("input Counting number: ");
    unsigned int M = 0;
    scanf("%u", &M);

    printf("the one who lived is #%d\n", josephus(T, M));
    return 0;
}
